package problem143_Reorder_List;

import problem82_Remove_Duplicates_from_Sorted_List2.ListNode;

public class Solution {
	 public void reorderList(ListNode head) {
		if(head==null||head.next==null||head.next.next==null) return;
		ListNode mid=getMiddle(head);
		ListNode right=reverse(mid);
		ListNode left=head;
		while(left.next!=null){
			 ListNode tmp1=right.next;
			 ListNode tmp2=left.next;
			 right.next=left.next;
			 left.next=right;
			 left=tmp2;
			 right=tmp1;
		}
		left.next=right;
	 }
	 
	 private ListNode getMiddle(ListNode head){
		 ListNode fast=head,slow=head,pre=head;
		 while(fast!=null&&fast.next!=null){
			 pre=slow;
			 slow=slow.next;
			 fast=fast.next.next;
		 }
		 pre.next=null;
		 return slow;
	 }
	 
	 private ListNode reverse(ListNode head){
		 ListNode dummy=new ListNode(-1);
		 while(head!=null){
			 ListNode tmp=head.next;
			 head.next=dummy.next;
			 dummy.next=head;
			 head=tmp;
		 }
		 return dummy.next;
	 }
	 
	 public static void main(String[] args){
		 ListNode head=new ListNode(1);
		 new Solution().reorderList(head);
	 }
}
